{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: # Check if There Is a Valid Parentheses String Path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: hasValidPath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #检查是否有合法括号字符串路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个括号字符串是一个 <strong>非空</strong>&nbsp;且只包含&nbsp;<code>'('</code>&nbsp;和&nbsp;<code>')'</code>&nbsp;的字符串。如果下面&nbsp;<strong>任意</strong>&nbsp;条件为&nbsp;<strong>真</strong>&nbsp;，那么这个括号字符串就是&nbsp;<strong>合法的</strong>&nbsp;。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>字符串是&nbsp;<code>()</code>&nbsp;。</li>\n",
    "\t<li>字符串可以表示为&nbsp;<code>AB</code>（<code>A</code>&nbsp;连接&nbsp;<code>B</code>），<code>A</code> 和&nbsp;<code>B</code>&nbsp;都是合法括号序列。</li>\n",
    "\t<li>字符串可以表示为&nbsp;<code>(A)</code>&nbsp;，其中&nbsp;<code>A</code>&nbsp;是合法括号序列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个&nbsp;<code>m x n</code>&nbsp;的括号网格图矩阵&nbsp;<code>grid</code>&nbsp;。网格图中一个&nbsp;<strong>合法括号路径</strong>&nbsp;是满足以下所有条件的一条路径：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>路径开始于左上角格子&nbsp;<code>(0, 0)</code>&nbsp;。</li>\n",
    "\t<li>路径结束于右下角格子&nbsp;<code>(m - 1, n - 1)</code>&nbsp;。</li>\n",
    "\t<li>路径每次只会向 <strong>下</strong>&nbsp;或者向 <strong>右</strong>&nbsp;移动。</li>\n",
    "\t<li>路径经过的格子组成的括号字符串是<strong>&nbsp;合法</strong>&nbsp;的。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果网格图中存在一条 <strong>合法括号路径</strong>&nbsp;，请返回&nbsp;<code>true</code>&nbsp;，否则返回&nbsp;<code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/15/example1drawio.png\" style=\"width: 521px; height: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>grid = [[\"(\",\"(\",\"(\"],[\")\",\"(\",\")\"],[\"(\",\"(\",\")\"],[\"(\",\"(\",\")\"]]\n",
    "<b>输出：</b>true\n",
    "<b>解释：</b>上图展示了两条路径，它们都是合法括号字符串路径。\n",
    "第一条路径得到的合法字符串是 \"()(())\" 。\n",
    "第二条路径得到的合法字符串是 \"((()))\" 。\n",
    "注意可能有其他的合法括号字符串路径。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/15/example2drawio.png\" style=\"width: 165px; height: 165px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>grid = [[\")\",\")\"],[\"(\",\"(\"]]\n",
    "<b>输出：</b>false\n",
    "<b>解释：</b>两条可行路径分别得到 \"))(\" 和 \")((\" 。由于它们都不是合法括号字符串，我们返回 false 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 100</code></li>\n",
    "\t<li><code>grid[i][j]</code>&nbsp;要么是&nbsp;<code>'('</code>&nbsp;，要么是&nbsp;<code>')'</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-there-is-a-valid-parentheses-string-path](https://leetcode.cn/problems/check-if-there-is-a-valid-parentheses-string-path/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-there-is-a-valid-parentheses-string-path](https://leetcode.cn/problems/check-if-there-is-a-valid-parentheses-string-path/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"(\",\"(\",\"(\"],[\")\",\"(\",\")\"],[\"(\",\"(\",\")\"],[\"(\",\"(\",\")\"]]', '[[\")\",\")\"],[\"(\",\"(\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        if grid[0][0] == ')': return False\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        states = [0]*n\n",
    "        for r, row in enumerate(grid):\n",
    "            last = 0 if r else 1\n",
    "            for c, (s, v) in enumerate(zip(states, row)):\n",
    "                last = last | s\n",
    "                if v == '(':\n",
    "                    last <<=1\n",
    "                else:\n",
    "                    last >>= 1\n",
    "                states[c] = last\n",
    "        return states[-1] & 1\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        if (m+n) % 2 == 0 or grid[0][0] == ')' or grid[m-1][n-1] == '(':\n",
    "            return False\n",
    "        \n",
    "        # 栈存储「四元组」：(i, j, left左括号数目, right右括号数目)\n",
    "        stack = [(0,0, 1,0)]\n",
    "        visited = set([(0,0,1,0)])\n",
    "        \n",
    "        while stack:\n",
    "            i, j, left, right = stack.pop()     # 后进先出\n",
    "            if i==m-1 and j==n-1 and left==right:\n",
    "                return True\n",
    "\n",
    "            # 剩余格子数 < 左括号与右括号的差值\n",
    "            if (m+n-1) - (i+j+1) < left - right:    \n",
    "                continue\n",
    "            \n",
    "            # 常规BFS：向右/下移动\n",
    "            for dx, dy in [(0,1),(1,0)]:\n",
    "                x, y = i+dx, j+dy\n",
    "                if 0<=x<m and 0<=y<n:\n",
    "                    if grid[x][y] == ')':   # 右括号+1？【需满足：左括号数目>=右括号数目】\n",
    "                        if right+1 <= left and (x, y, left, right+1) not in visited:\n",
    "                            stack.append((x, y, left, right+1))\n",
    "                            visited.add((x, y, left, right+1))\n",
    "                    else:                   # 左括号+1？\n",
    "                        if (x,y,left+1,right) not in visited:\n",
    "                            stack.append((x, y, left+1, right))\n",
    "                            visited.add((x, y, left+1, right))\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        stack = []\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        if (m+n) % 2 == 0 or grid[0][0] == ')' or grid[m-1][n-1] == '(':\n",
    "            return False\n",
    "        \n",
    "        stack.append([0, 0, 1])\n",
    "        cnt = 0\n",
    "        visited = set()\n",
    "        while stack:\n",
    "            cnt += 1\n",
    "            x, y, left = stack.pop()\n",
    "            if (m+n-1) - (x+y+1) < left:    \n",
    "                continue\n",
    "            if (x, y) == (m-1, n-1):\n",
    "                if left == 0:\n",
    "                    return True\n",
    "                continue\n",
    "            for x_, y_ in [[x+1, y], [x, y+1]]:\n",
    "                if 0 <= x_ < m and 0 <= y_ < n:\n",
    "                    cur_left = left\n",
    "                    if grid[x_][y_] == \"(\":\n",
    "                        cur_left += 1\n",
    "                    else:\n",
    "                        cur_left -= 1\n",
    "                    if cur_left < 0:\n",
    "                        continue\n",
    "                    if (x_, y_, cur_left) in visited:\n",
    "                        continue\n",
    "                    visited.add((x_, y_, cur_left))\n",
    "                    stack.append((x_, y_, cur_left))\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        if (n + m) % 2 == 0 or grid[0][0] == ')': return False\n",
    "        @cache\n",
    "        def f(x, y, tot):\n",
    "            if tot < 0: return False\n",
    "            if x == n - 1 and y == m - 1:\n",
    "                return tot == 0\n",
    "            if x < n - 1:\n",
    "                tot += 1 if grid[x+1][y] == '(' else -1\n",
    "                if f(x + 1, y, tot): return True\n",
    "                tot -= 1 if grid[x+1][y] == '(' else -1\n",
    "            if y < m - 1:\n",
    "                tot += 1 if grid[x][y+1] == '(' else -1\n",
    "                if f(x, y + 1, tot): return True\n",
    "                tot -= 1 if grid[x][y+1] == '(' else -1\n",
    "            return False\n",
    "        ans = f(0, 0, 1)\n",
    "        f.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0:\n",
    "            return False\n",
    "        if grid[0][0] == ')':\n",
    "            return False\n",
    "        dp = [[] for _ in range(n)]\n",
    "        dp[0] = [1]\n",
    "        row0 = grid[0]\n",
    "        for c in range(1, n):\n",
    "            if row0[c] == '(':\n",
    "                dp[c] = [dp[c-1][0] + 1]\n",
    "            else:\n",
    "                if dp[c-1][0] > 0:\n",
    "                    dp[c] = [dp[c-1][0] - 1]\n",
    "                else:\n",
    "                    break\n",
    "        for r in range(1, m):\n",
    "            row = grid[r]\n",
    "            if len(dp[0]) == 1:\n",
    "                if row[0] == '(':\n",
    "                    dp[0][0] += 1\n",
    "                else:\n",
    "                    if dp[0][0] > 0:\n",
    "                        dp[0][0] -= 1\n",
    "                    else:\n",
    "                        dp[0] = []\n",
    "            for c in range(1, n):\n",
    "                d = 1 if row[c] == '(' else -1\n",
    "                a1, a2, b = dp[c-1], dp[c], []\n",
    "                n1, n2, i1, i2 = len(a1), len(a2), 0, 0\n",
    "                while i1 < n1 and a1[i1] + d < 0:\n",
    "                    i1 += 1\n",
    "                while i2 < n2 and a2[i2] + d < 0:\n",
    "                    i2 += 1\n",
    "                while i1 < n1 and i2 < n2:\n",
    "                    if a1[i1] < a2[i2]:\n",
    "                        b.append(a1[i1] + d)\n",
    "                        i1 += 1\n",
    "                    elif a2[i2] < a1[i1]:\n",
    "                        b.append(a2[i2] + d)\n",
    "                        i2 += 1\n",
    "                    else:\n",
    "                        b.append(a1[i1] + d)\n",
    "                        i1 += 1\n",
    "                        i2 += 1\n",
    "                while i1 < n1:\n",
    "                    b.append(a1[i1] + d)\n",
    "                    i1 += 1\n",
    "                while i2 < n2:\n",
    "                    b.append(a2[i2] + d)\n",
    "                    i2 += 1\n",
    "                dp[c] = b\n",
    "        return 0 in dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "       @cache\n",
    "       def dfs(i: int, j: int, d: int) -> bool:\n",
    "          if i >= m or j >= n:\n",
    "             return False\n",
    "          d += 1 if grid[i][j] == '(' else -1\n",
    "          if d < 0:\n",
    "             return False\n",
    "          if i == m - 1 and j == n - 1:\n",
    "             return d == 0\n",
    "          if d > m - i - 1 + n - j - 1:\n",
    "             return False\n",
    "          return dfs(i + 1, j, d) or dfs(i, j + 1, d)\n",
    "       m = len(grid)\n",
    "       n = len(grid[0])\n",
    "       if ((n + m - 1) & 1) == 1 or grid[0][0] == ')' or grid[m - 1][n - 1] == '(':\n",
    "          return False\n",
    "       return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        if (m + n) % 2 == 0 or grid[0][0] == ')' or grid[m - 1][n - 1] == '(': return False # 剪枝\n",
    "        @cache # 效果类似vis数组\n",
    "        def dfs(x:int, y:int, c:int)-> bool:\n",
    "            if c > m - x + n - y + 1: return False # 剪枝：即使后面都是 ')'，也不能将c减为0\n",
    "            if x == m - 1 and y == n - 1: return c == 1 # 终点一定是')'\n",
    "\n",
    "            c += 1 if grid[x][y] == '(' else - 1\n",
    "            return c >= 0 and (x < m - 1 and dfs(x + 1, y, c) or y < n - 1 and dfs(x, y + 1, c)) # 往下或往右\n",
    "        return dfs(0, 0, 0) # 起点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0 or grid[0][0] == ')' or grid[m - 1][n - 1] == '(': return False  # 剪枝\n",
    "\n",
    "        @cache  # 效果类似 vis 数组\n",
    "        def dfs(x: int, y: int, c: int) -> bool:\n",
    "            if c > m - x + n - y - 1: return False  # 剪枝：即使后面都是 ')' 也不能将 c 减为 0\n",
    "            if x == m - 1 and y == n - 1: return c == 1  # 终点一定是 ')'\n",
    "            c += 1 if grid[x][y] == '(' else -1\n",
    "            return c >= 0 and (x < m - 1 and dfs(x + 1, y, c) or y < n - 1 and dfs(x, y + 1, c))  # 往下或者往右\n",
    "        return dfs(0, 0, 0)  # 起点\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if grid[0][0] == ')' or grid[-1][-1] == '(' or (m + n - 1) & 1:\n",
    "            return False\n",
    "        print(m, n)\n",
    "        @cache\n",
    "        def dfs(i, j, c):\n",
    "            # if m - i + n - j - 1 < c:\n",
    "            #     return False\n",
    "            if i == m - 1 and j == n - 1 and c == 0:\n",
    "                return True\n",
    "            if i + 1 < m:\n",
    "                if grid[i + 1][j] == '(' and dfs(i + 1, j, c + 1):\n",
    "                    return True\n",
    "                elif grid[i + 1][j] == ')' and c - 1 >= 0 and dfs(i + 1, j, c - 1):\n",
    "                    return True\n",
    "            if j + 1 < n:\n",
    "                if grid[i][j + 1] == '(' and dfs(i, j + 1, c + 1):\n",
    "                    return True\n",
    "                elif grid[i][j + 1] == ')' and c - 1 >= 0 and dfs(i, j + 1, c - 1):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(0, 0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0 or grid[0][0] == ')' or grid[m - 1][n - 1] == '(': return False  # 剪枝\n",
    "\n",
    "        @cache  # 效果类似 vis 数组\n",
    "        def dfs(x: int, y: int, c: int) -> bool:\n",
    "            if c > m - x + n - y - 1: return False  # 剪枝：即使后面都是 ')' 也不能将 c 减为 0\n",
    "            if x == m - 1 and y == n - 1: return c == 1  # 终点一定是 ')'\n",
    "            c += 1 if grid[x][y] == '(' else -1\n",
    "            return c >= 0 and (x < m - 1 and dfs(x + 1, y, c) or y < n - 1 and dfs(x, y + 1, c))  # 往下或者往右\n",
    "        return dfs(0, 0, 0)  # 起点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "\n",
    "        if grid[0][0] ==')' or grid[n - 1][m - 1] == '(' or (n + m) % 2 == 0 :\n",
    "            return False\n",
    "        \n",
    "        @cache\n",
    "\n",
    "        def dfs(i: int , j: int, now: int) -> bool:\n",
    "\n",
    "            if now > n - i + m - j - 1:\n",
    "                return False\n",
    "\n",
    "            if i == n - 1 and j == m - 1:\n",
    "                return now == 1\n",
    "            \n",
    "            now += 1 if grid[i][j] == '(' else -1\n",
    "\n",
    "            return now >= 0 and (i < n - 1 and dfs(i + 1, j, now) or j < m - 1 and dfs(i, j + 1, now))\n",
    "\n",
    "        return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0 or grid[0][0] == ')' or grid[m - 1][n - 1] == '(': return False  # 剪枝\n",
    "\n",
    "        @cache  # 效果类似 vis 数组\n",
    "        def dfs(x: int, y: int, c: int) -> bool:\n",
    "            if c > m - x + n - y - 1: return False  # 剪枝：即使后面都是 ')' 也不能将 c 减为 0\n",
    "            if x == m - 1 and y == n - 1: return c == 1  # 终点一定是 ')'\n",
    "            c += 1 if grid[x][y] == '(' else -1\n",
    "            return c >= 0 and (x < m - 1 and dfs(x + 1, y, c) or y < n - 1 and dfs(x, y + 1, c))  # 往下或者往右\n",
    "        return dfs(0, 0, 0)  # 起点\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        if (m+n-1)%2==1 or grid[0][0]==')'or grid[m-1][n-1]=='(':return False\n",
    "        @lru_cache(None)\n",
    "        def dfs(x,y,c):#c表示进入格子x,y之前的状态，c是字符串平衡度\n",
    "            if c>m-x+n-y-1:return False #剪枝，及时后面都是)也不能将c剪为0\n",
    "            if x==m-1 and y==n-1:return c==1#终点必须是），因此进终点前的状态值一定是1\n",
    "            c+=1 if grid[x][y]=='('else -1\n",
    "            return c>=0 and ((x<m-1 and dfs(x+1,y,c)) or y<n-1 and dfs(x,y+1,c))#往下，或者往右\n",
    "        return dfs(0,0,0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if grid[0][0] == ')' or grid[-1][-1] == '(' or (m + n - 1) & 1:\n",
    "            return False\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j, c):\n",
    "            if m - i + n - j - 1 < c:\n",
    "                return False\n",
    "            if i == m - 1 and j == n - 1 and c == 1:\n",
    "                return True\n",
    "            c += 1 if grid[i][j] == '(' else -1\n",
    "            return c >= 0 and (i + 1 < m and dfs(i + 1, j, c) or j + 1 < n and dfs(i, j + 1, c))\n",
    "        return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        if grid[0][0] == ')' or grid[n - 1][m - 1] == '(' or (n + m) % 2 == 0 :\n",
    "            return False\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, c: int) -> bool:\n",
    "            if c > m - i + n - j - 1 : return False\n",
    "            if i == n -1 and j == m - 1:\n",
    "                return c == 1\n",
    "            c += 1 if grid[i][j] == '(' else -1\n",
    "\n",
    "            return c >= 0 and (i < n - 1 and dfs(i + 1, j, c) or  j < m - 1 and dfs(i, j + 1, c))\n",
    "        return dfs(0, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0 or grid[0][0] == ')' or grid[m - 1][n - 1] == \"(\": return False\n",
    "        @cache\n",
    "        def dfs(x: int, y: int, c: int) -> bool:\n",
    "            if c > m - x + n - y - 1: return False\n",
    "            if x == m - 1 and y == n - 1: return c == 1\n",
    "            c += 1 if grid[x][y] == '(' else -1\n",
    "            return c >= 0 and (x < m - 1 and dfs(x + 1, y, c) or y < n - 1 and dfs(x, y + 1, c))\n",
    "        return dfs(0, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "\n",
    "        if grid[0][0] ==')' or grid[n - 1][m - 1] == '(' or (n + m) % 2 == 0 :\n",
    "            return False\n",
    "        \n",
    "        @cache\n",
    "\n",
    "        def dfs(i: int , j: int, now: int) -> bool:\n",
    "\n",
    "            if i == n - 1 and j == m - 1:\n",
    "                return now == 1\n",
    "            \n",
    "            now += 1 if grid[i][j] == '(' else -1\n",
    "\n",
    "            return now >= 0 and (i < n - 1 and dfs(i + 1, j, now) or j < m - 1 and dfs(i, j + 1, now))\n",
    "\n",
    "        return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        if (m + n - 1) & 1  or grid[0][0] == ')' or grid[m - 1][n - 1] == '(': \n",
    "            return False\n",
    "        @cache\n",
    "        def dfs(x=0,y=0,count=0):\n",
    "            if grid[x][y] == '(':\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "            if count < 0 :\n",
    "                return False\n",
    "            if x==m-1 and y==n-1:\n",
    "                return count == 0\n",
    "            for i,j in [[x+1,y],[x,y+1]]:\n",
    "                if not(0<=i<m and 0<=j<n):\n",
    "                    continue\n",
    "                if dfs(i,j,count):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        if grid[0][0] == ')' or grid[n - 1][m - 1] == '(' or (n + m) % 2 == 0 :\n",
    "            return False\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, c: int) -> bool:\n",
    "            if c > m - i + n - j - 1 : return False\n",
    "            if i == n -1 and j == m - 1:\n",
    "                return c == 1\n",
    "            c += 1 if grid[i][j] == '(' else -1\n",
    "\n",
    "            return c >= 0 and (i < n - 1 and dfs(i + 1, j, c) or  j < m - 1 and dfs(i, j + 1, c))\n",
    "        return dfs(0, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if grid[0][0] == ')' or grid[-1][-1] == '(' or (m + n - 1) & 1:\n",
    "            return False\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j, c):\n",
    "            # if m - i + n - j - 1 < c:\n",
    "            #     return False\n",
    "            if i == m - 1 and j == n - 1 and c == 0:\n",
    "                return True\n",
    "            if i + 1 < m:\n",
    "                if grid[i + 1][j] == '(' and dfs(i + 1, j, c + 1):\n",
    "                    return True\n",
    "                elif grid[i + 1][j] == ')' and c - 1 >= 0 and dfs(i + 1, j, c - 1):\n",
    "                    return True\n",
    "            if j + 1 < n:\n",
    "                if grid[i][j + 1] == '(' and dfs(i, j + 1, c + 1):\n",
    "                    return True\n",
    "                elif grid[i][j + 1] == ')' and c - 1 >= 0 and dfs(i, j + 1, c - 1):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(0, 0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0 or grid[0][0] == ')' or grid[m - 1][n - 1] == '(': return False  # 剪枝\n",
    "\n",
    "        @cache  # 效果类似 vis 数组\n",
    "        def dfs(x: int, y: int, c: int) -> bool:\n",
    "            if c > m - x + n - y - 1: return False  # 剪枝：即使后面都是 ')' 也不能将 c 减为 0\n",
    "            if x == m - 1 and y == n - 1: return c == 1  # 终点一定是 ')'\n",
    "            c += 1 if grid[x][y] == '(' else -1\n",
    "            return c >= 0 and (x < m - 1 and dfs(x + 1, y, c) or y < n - 1 and dfs(x, y + 1, c))  # 往下或者往右\n",
    "        return dfs(0, 0, 0)  # 起点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0 or grid[0][0] == ')' or grid[m - 1][n - 1] == '(': return False  # 剪枝\n",
    "\n",
    "        @cache  # 效果类似 vis 数组\n",
    "        def dfs(x: int, y: int, c: int) -> bool:\n",
    "            if c > m - x + n - y - 1: return False  # 剪枝：即使后面都是 ')' 也不能将 c 减为 0\n",
    "            if x == m - 1 and y == n - 1: return c == 1  # 终点一定是 ')'\n",
    "            c += 1 if grid[x][y] == '(' else -1\n",
    "            return c >= 0 and (x < m - 1 and dfs(x + 1, y, c) or y < n - 1 and dfs(x, y + 1, c))  # 往下或者往右\n",
    "        return dfs(0, 0, 0)  # 起点\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0 or grid[0][0] == ')' or grid[m - 1][n - 1] == '(': return False  # 剪枝\n",
    "\n",
    "        @cache  # 效果类似 vis 数组\n",
    "        def dfs(x: int, y: int, c: int) -> bool:\n",
    "            if c > m - x + n - y - 1: return False  # 剪枝：即使后面都是 ')' 也不能将 c 减为 0\n",
    "            if x == m - 1 and y == n - 1: return c == 1  # 终点一定是 ')'\n",
    "            c += 1 if grid[x][y] == '(' else -1\n",
    "            return c >= 0 and (x < m - 1 and dfs(x + 1, y, c) or y < n - 1 and dfs(x, y + 1, c))  # 往下或者往右\n",
    "        return dfs(0, 0, 0)  # 起点\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import cache\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        if (m + n - 1) & 1  or grid[0][0] == ')' or grid[m - 1][n - 1] == '(': \n",
    "            return False\n",
    "\n",
    "        @cache\n",
    "        def dfs(x=0, y=0, count=0):\n",
    "            if grid[x][y] == '(':\n",
    "                count += 1\n",
    "            else:\n",
    "                count -= 1\n",
    "\n",
    "            if count < 0:\n",
    "                return False\n",
    "\n",
    "            if x == m-1 and y == n-1:\n",
    "                return count == 0\n",
    "\n",
    "            for i, j in [[x+1, y], [x, y+1]]:\n",
    "                if 0 <= i < m and 0 <= j < n:\n",
    "                    if dfs(i, j, count):\n",
    "                        return True\n",
    "\n",
    "            return False\n",
    "        \n",
    "        return dfs()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m + n) % 2 == 0:\n",
    "            return False\n",
    "        \n",
    "        @cache\n",
    "        def dfs(x, y, cnt, flag):\n",
    "            if flag:\n",
    "                return flag\n",
    "            if grid[x][y] == \"(\":\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "            if x == m - 1 and y == n - 1 and cnt == 0:\n",
    "                flag = True\n",
    "            if cnt >= 0:\n",
    "                if x < m - 1:\n",
    "                    flag |= dfs(x + 1, y, cnt, flag)\n",
    "                if y < n - 1:\n",
    "                    flag |= dfs(x, y + 1, cnt, flag)\n",
    "            return flag\n",
    "        return dfs(0,0, 0, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid) -> bool:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        dp=[[[]]*n for i in range(m)]\n",
    "        if grid[0][0]=='(':\n",
    "            dp[0][0]=[1]\n",
    "        else:\n",
    "            return False\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 and j==0:\n",
    "                    continue\n",
    "                if i==0:\n",
    "                    if dp[i][j-1]!=None:\n",
    "                        next=set()\n",
    "                        s=dp[i][j-1]\n",
    "                        if grid[i][j]=='(':\n",
    "                            flag=1\n",
    "                        else:\n",
    "                            flag=-1\n",
    "                        for k in range(len(s)):\n",
    "                            if s[k]>=0 and s[k]+flag>=0:\n",
    "                                next=next|{s[k]+flag}\n",
    "                        if next==set():\n",
    "                            dp[i][j]=None\n",
    "                        else:\n",
    "                            dp[i][j]=list(next)\n",
    "                    else:\n",
    "                        dp[i][j]=None\n",
    "                        \n",
    "                elif j==0:\n",
    "                    if dp[i-1][j]!=None:\n",
    "                        next=set()\n",
    "                        s=dp[i-1][j]\n",
    "                        if grid[i][j]=='(':\n",
    "                            flag=1\n",
    "                        else:\n",
    "                            flag=-1\n",
    "                        for k in range(len(s)):\n",
    "                            if s[k]>=0 and s[k]+flag>=0:\n",
    "                                next=next|{s[k]+flag}\n",
    "                        if next==set():\n",
    "                            dp[i][j]=None\n",
    "                        else:\n",
    "                            dp[i][j]=list(next)\n",
    "                    else:\n",
    "                        dp[i][j]=None\n",
    "\n",
    "                else:\n",
    "                    if grid[i][j]=='(':\n",
    "                        flag=1\n",
    "                    else:\n",
    "                        flag=-1\n",
    "                    next=set()\n",
    "                    if dp[i][j-1]!=None:\n",
    "                        s=dp[i][j-1]\n",
    "                        for k in range(len(s)):\n",
    "                            if  s[k]+flag>=0:\n",
    "                                next=next|{s[k]+flag}\n",
    "                    if dp[i-1][j]!=None:\n",
    "                        s=dp[i-1][j]\n",
    "                        for k in range(len(s)):\n",
    "                            if  s[k]+flag>=0:\n",
    "                                next=next|{s[k]+flag}\n",
    "                        if next==set():\n",
    "                            dp[i][j]=None\n",
    "                        else:\n",
    "                            dp[i][j]=list(next)\n",
    "                    if dp[i][j-1]==None and dp[i-1][j]==None:\n",
    "                        dp[i][j]=None\n",
    "        if dp[-1][-1] !=None and 0 in dp[-1][-1]:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        # m是行，n是列\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        @cache\n",
    "        def subvalid(x,y,count):\n",
    "            if x > m - 1 or y > n - 1:\n",
    "                return False\n",
    "            else:\n",
    "                if grid[x][y] == \"(\":\n",
    "                    count += 1\n",
    "                else:\n",
    "                    count -= 1\n",
    "            \n",
    "            if count < 0:\n",
    "                return False\n",
    "\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                if count == 0:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            else:            \n",
    "                return subvalid(x, y+1, count) or subvalid(x+1, y, count)\n",
    "\n",
    "        if (m + n) % 2 == 0:\n",
    "            return False\n",
    "        else:\n",
    "            return subvalid(0,0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        n,m = len(grid), len(grid[0])\n",
    "        if (n+m)%2 == 0:\n",
    "            return False\n",
    "        @cache\n",
    "        def f(x,y,tar)->bool:\n",
    "            if x>=n or y>=m or tar > 0:\n",
    "                return False\n",
    "            if x==n-1 and y==m-1:\n",
    "                return grid[x][y] == ')' and tar == -1\n",
    "            d = 1 if grid[x][y] == '(' else -1\n",
    "            return f(x+1,y,tar-d) or f(x,y+1,tar-d)\n",
    "\n",
    "        return f(0,0,0)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if (m & 1 and n & 1) or grid[0][0] == ')':\n",
    "            return False\n",
    "        max_diff = (m + n) // 2\n",
    "        f = [[[False] * (max_diff + 1) for i in range(n)] for j in range(m)]\n",
    "        f[0][0][1] = True\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                d = -1 if grid[i][j] == '(' else 1\n",
    "                for diff in range(min(max_diff, i + j + 1) + 1):\n",
    "                    if diff + d < 0 or diff + d > max_diff:\n",
    "                        continue\n",
    "                    if (i and f[i - 1][j][diff + d]) or (j and f[i][j - 1][diff + d]):\n",
    "                        f[i][j][diff] = 1\n",
    "        return f[m - 1][n - 1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        if (m + n - 1) % 2 or grid[0][0] != \"(\" or grid[m-1][n-1] != \")\":\n",
    "            return False\n",
    "    \n",
    "        f = [[[False] * (m + n) for _ in range(n)] for _ in range(m)]\n",
    "        f[0][0][1] = True\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == j == 0:\n",
    "                    continue\n",
    "                val = 1 if grid[i][j] == \"(\" else -1\n",
    "                for k in range(m + n):\n",
    "                    if k - val < 0:\n",
    "                        continue\n",
    "                    if k - val >= m + n:\n",
    "                        continue\n",
    "                    if i > 0:\n",
    "                        f[i][j][k] |= f[i-1][j][k-val]\n",
    "                    if j > 0:\n",
    "                        f[i][j][k] |= f[i][j-1][k-val]\n",
    "        \n",
    "        return f[m-1][n-1][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        if grid[0][0] == ')':\n",
    "            return False\n",
    "        else:\n",
    "            grid[0][0] = set([1])\n",
    "        \n",
    "        n, m = len(grid), len(grid[0])\n",
    "        for i in range(1, n):\n",
    "            offset = 1 if grid[i][0] == '(' else -1\n",
    "            grid[i][0] = set()\n",
    "            for v in grid[i-1][0]:\n",
    "                if v + offset >= 0:\n",
    "                    grid[i][0].add(v + offset)\n",
    "        for j in range(1, m):\n",
    "            offset = 1 if grid[0][j] == '(' else -1\n",
    "            grid[0][j] = set()\n",
    "            for v in grid[0][j-1]:\n",
    "                if v + offset >= 0:\n",
    "                    grid[0][j].add(v + offset)\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                offset = 1 if grid[i][j] == '(' else -1\n",
    "                grid[i][j] = set()\n",
    "                for v in grid[i-1][j]:\n",
    "                    if v + offset >= 0:\n",
    "                        grid[i][j].add(v + offset)\n",
    "                for v in grid[i][j-1]:\n",
    "                    if v + offset >= 0:\n",
    "                        grid[i][j].add(v + offset)\n",
    "        \n",
    "        return 0 in grid[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        if grid[0][0]==')':\n",
    "            return False \n",
    "        \n",
    "        brackets = collections.defaultdict(set)\n",
    "\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if i==0 and j==0:\n",
    "                    brackets[(0,0)].add(1)\n",
    "                    continue \n",
    "\n",
    "                y = 1 if grid[i][j]=='(' else -1\n",
    "                if i-1>=0:\n",
    "                    for x in brackets[(i-1,j)]:\n",
    "                        if x+y>=0:\n",
    "                            brackets[(i,j)].add(x+y)\n",
    "                if j-1>=0:\n",
    "                    for x in brackets[(i,j-1)]:\n",
    "                        if x+y>=0:\n",
    "                            brackets[(i,j)].add(x+y)\n",
    "        \n",
    "        return 0 in brackets[(n-1,m-1)]\n",
    "\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        stack = []\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        if grid[0][0] == \")\":\n",
    "            return False\n",
    "        \n",
    "        stack.append([0, 0, 1])\n",
    "        cnt = 0\n",
    "        visited = set()\n",
    "        while stack:\n",
    "            cnt += 1\n",
    "            x, y, left = stack.pop()\n",
    "            if (m+n-1) - (x+y+1) < left:    \n",
    "                continue\n",
    "            if (x, y) == (m-1, n-1):\n",
    "                if left == 0:\n",
    "                    return True\n",
    "                continue\n",
    "            for x_, y_ in [[x+1, y], [x, y+1]]:\n",
    "                if 0 <= x_ < m and 0 <= y_ < n:\n",
    "                    cur_left = left\n",
    "                    if grid[x_][y_] == \"(\":\n",
    "                        cur_left += 1\n",
    "                    else:\n",
    "                        cur_left -= 1\n",
    "                    if cur_left < 0:\n",
    "                        continue\n",
    "                    if (x_, y_, cur_left) in visited:\n",
    "                        continue\n",
    "                    visited.add((x_, y_, cur_left))\n",
    "                    stack.append((x_, y_, cur_left))\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        if (m+n) % 2 == 0 or grid[0][0] == ')' or grid[m-1][n-1] == '(':\n",
    "            return False\n",
    "        \n",
    "        # 双端队列存储「四元组」：(i, j, left左括号数目, right右括号数目)\n",
    "        deque = collections.deque([(0,0, 1,0)])\n",
    "        visited = set([(0,0,1,0)])\n",
    "        \n",
    "        while deque:\n",
    "            i, j, left, right = deque.popleft()\n",
    "            if i==m-1 and j==n-1 and left==right:\n",
    "                return True\n",
    "\n",
    "            # 剩余格子数 < 左括号与右括号的差值\n",
    "            if (m+n-1) - (i+j+1) < left - right:    \n",
    "                continue\n",
    "            \n",
    "            # 常规BFS：向右/下移动\n",
    "            for dx, dy in [(0,1),(1,0)]:\n",
    "                x, y = i+dx, j+dy\n",
    "                if 0<=x<m and 0<=y<n:\n",
    "                    if grid[x][y] == ')':   # 右括号+1？【需满足：左括号数目>=右括号数目】\n",
    "                        if right+1 <= left and (x, y, left, right+1) not in visited:\n",
    "                            deque.append((x, y, left, right+1))\n",
    "                            visited.add((x, y, left, right+1))\n",
    "                    else:                   # 左括号+1？\n",
    "                        if (x,y,left+1,right) not in visited:\n",
    "                            deque.append((x, y, left+1, right))\n",
    "                            visited.add((x, y, left+1, right))\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if grid[-1][-1] == '(':\n",
    "            return False\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y, p):\n",
    "            if not (0 <= x < m and 0 <= y < n):\n",
    "                return False\n",
    "\n",
    "            if grid[x][y] == '(':\n",
    "                p += 1\n",
    "            else:\n",
    "                p -= 1\n",
    "\n",
    "            if p < 0:\n",
    "                return False\n",
    "            if x == m - 1 and y == n - 1 and p == 0:\n",
    "                return True\n",
    "            \n",
    "            return dfs(x + 1, y, p) or dfs(x, y + 1, p)\n",
    "\n",
    "        ans = dfs(0, 0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if grid[0][0] == ')': return False\n",
    "        if grid[-1][-1] == '(': return False\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        \n",
    "        @cache\n",
    "        def dfs(l, r, x, y):\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return l == r + 1\n",
    "            if l < r: \n",
    "                return False\n",
    "            \n",
    "            if grid[x][y] == '(':\n",
    "                l += 1\n",
    "            else:\n",
    "                r += 1\n",
    "            \n",
    "            for nx, ny in (x+1, y),(x,y+1):\n",
    "                if not (0 <= nx < m and 0 <= ny < n): continue\n",
    "                if vis[nx][ny]: continue\n",
    "                vis[nx][ny] = True    \n",
    "                if dfs(l, r, nx, ny):\n",
    "                    return True\n",
    "                vis[nx][ny] = False\n",
    "            return False\n",
    "        \n",
    "        return dfs(0,0,0,0)\n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j, left, right):\n",
    "            if left < right:\n",
    "                return False\n",
    "            if i == m-1 and j == n-1 and left == right:\n",
    "                return True\n",
    "            for dx, dy in [(0, 1), (1, 0)]:\n",
    "                x, y = i + dx, j + dy\n",
    "                if 0 <= x < m and 0 <= y < n:\n",
    "                    if grid[x][y] == '(':\n",
    "                        if dfs(x, y, left+1, right):\n",
    "                            return True\n",
    "                    elif dfs(x, y, left, right+1):\n",
    "                        return True\n",
    "            return False\n",
    "        return dfs(0, 0, 1, 0) if grid[0][0] == '(' else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "       @cache\n",
    "       def dfs(i: int, j: int, d: int) -> bool:\n",
    "          if i >= m or j >= n:\n",
    "             return False\n",
    "          d += 1 if grid[i][j] == '(' else -1\n",
    "          if d < 0:\n",
    "             return False\n",
    "          if i == m - 1 and j == n - 1:\n",
    "             return d == 0\n",
    "          if d > m - i - 1 + n - j - 1:\n",
    "             return False\n",
    "          return dfs(i + 1, j, d) or dfs(i, j + 1, d)\n",
    "       m = len(grid)\n",
    "       n = len(grid[0])\n",
    "       return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j, pre):\n",
    "            if grid[i][j] == \")\":\n",
    "                if pre <= 0:\n",
    "                    return False\n",
    "                pre -= 1\n",
    "            else:\n",
    "                pre += 1\n",
    "            if i == m-1 and j == n-1:\n",
    "                return pre == 0\n",
    "            if i+1<m and dfs(i+1, j, pre):\n",
    "                return True\n",
    "            if j+1<n and dfs(i, j+1, pre):\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "       @cache\n",
    "       def dfs(i: int, j: int, d: int) -> bool:\n",
    "          if i >= m or j >= n:\n",
    "             return False\n",
    "          d += 1 if grid[i][j] == '(' else -1\n",
    "          if d < 0:\n",
    "             return False\n",
    "          if i == m - 1 and j == n - 1:\n",
    "             return d == 0\n",
    "          return dfs(i + 1, j, d) or dfs(i, j + 1, d)\n",
    "       m = len(grid)\n",
    "       n = len(grid[0])\n",
    "       return dfs(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m , n = len(grid) , len(grid[0])\n",
    "        @lru_cache(None)\n",
    "        def dfs(i , j , l , r):\n",
    "            if i >= m or j >= n:\n",
    "                return False\n",
    "            if grid[i][j] == '(':\n",
    "                l += 1\n",
    "            else:\n",
    "                r += 1\n",
    "            if i == m - 1 and j == n- 1:\n",
    "                if l == r :\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            if r > l:\n",
    "                return False\n",
    "\n",
    "            return dfs(i + 1,j,l,r) or dfs(i ,j + 1,l,r)\n",
    "        return dfs(0,0,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if grid[0][0] == ')': return False\n",
    "        if grid[-1][-1] == '(': return False\n",
    "\n",
    "        @cache\n",
    "        def dfs(l, r, x, y):\n",
    "            if not (0 <= x < m and 0 <= y < n): return False\n",
    "\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return l == r + 1\n",
    "            if l < r: \n",
    "                return False\n",
    "            \n",
    "            if grid[x][y] == '(':\n",
    "                l += 1\n",
    "            else:\n",
    "                r += 1\n",
    "            return dfs(l, r, x + 1, y) or dfs(l, r, x, y + 1)\n",
    "        \n",
    "        return dfs(0,0,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if grid[0][0] == ')': return False\n",
    "        if grid[-1][-1] == '(': return False\n",
    "        \n",
    "        @cache\n",
    "        def dfs(l, r, x, y):\n",
    "            if not (0 <= x < m and 0 <= y < n): return False\n",
    "            if x == m - 1 and y == n - 1:\n",
    "                return l == r + 1\n",
    "            if l < r: \n",
    "                return False\n",
    "            \n",
    "            if grid[x][y] == '(':\n",
    "                l += 1\n",
    "            else:\n",
    "                r += 1\n",
    "            \n",
    "            return dfs(l, r, x + 1, y) or dfs(l, r, x, y + 1)\n",
    "        \n",
    "        return dfs(0,0,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hasValidPath(self, grid: List[List[str]]) -> bool:\n",
    "        n,m = len(grid), len(grid[0])\n",
    "        @cache\n",
    "        def f(x,y,tar)->bool:\n",
    "            if x>=n or y>=m:\n",
    "                return False\n",
    "            if x==n-1 and y==m-1:\n",
    "                return grid[x][y] == ')' and tar == -1\n",
    "            if tar > 0:\n",
    "                return False\n",
    "            d = 1 if grid[x][y] == '(' else -1\n",
    "            return f(x+1,y,tar-d) or f(x,y+1,tar-d)\n",
    "\n",
    "        return f(0,0,0)\n",
    "\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
